The present invention relates to a method and a device for determining the length of a shortest path in a network. In particular, the present invention relates to the application of such a method and a device to road networks, for example in a road navigation device.
In general, the shortest path problem is the problem of finding a path between two nodes of a network such that the sum of the weights of its constituent edges is minimized. A practical example is finding the quickest way to get from one location to another on a road map; in this case, the vertices represent locations and the edges represent segments of road and are weighted by the time needed to travel that segment.
Formally, given a weighted graph (that is, a set V of vertices, a set E of edges, and a (real-valued) weight function f: E→R), and one element v of V, find a path P from v to each v′ of V so that
      ∑          p      ∈      P        ⁢      f    ⁡          (      p      )      is minimal among all paths connecting v to v′.
The classical way to compute the shortest path between two given nodes in a graph with given edge lengths is Dijkstra's algorithm. The asymptotic running time of Dijkstra's algorithm is O(m+n log m), where n is the number of nodes, and m is the number of edges. For graphs with constant degree, like for example road networks, this is O(n log n). Up to now, no better algorithm is known for computing the shortest path between two given nodes in a graph if no pre-processing is allowed and no assumptions on the graph, except for non-negative edge lengths, are made.
On the US road network, a good implementation of Dijkstra's algorithm on a single state-of-the-art PC takes a few seconds, on average, for a random query. For a random query, source and target are likely to be far away from each other, in which case Dijkstra's algorithm will settle a large portion of all nodes in the network before eventually reaching the target.
If, however, the topology of the graph or the network does not change (significantly) between queries, the above restrictions may be given up. Hence, the problem of determining the length of a shortest path in the network may be divided into the problem of pre-processing the network or creating a data structure from the network such that efficient queries become possible and the problem of efficiently querying that data structure. In other words, the network may be pre-processed in order to speed up the queries. Actual search in the network may then be carried out beforehand, thereby reducing computations to a simple lookup at query time.
However, a naïve approach would involve creating a lookup table for all possible queries concerning a given network. In order to store these distances, quadratic space would be needed. This would be prohibitive for e.g. the US road network, which has about 24 million nodes and 58 million edges.
An article by Gutman (“Reach-Based Routing: a new approach to shortest path algorithms optimized for road networks. Proceedings of the 6th Workshop on Algorithm Engineering and Experiments, 2004) proposes a general concept of edge levels for improving upon the naïve approach. Given an edge e that appears “in the middle” of a shortest paths, shortest with respect to travel time, between two nodes that are a certain distance d apart, distance with respect to some arbitrary other metric, e.g. Euclidean distance, the level of e is the higher, the larger d is. The article defines levels with respect to Euclidean distance, but notes that any metric can be used for the discrimination of the “in the middle” property. Simple algorithms are presented which compute upper bounds for the edge levels and instruments those to obtain more efficient exact shortest path queries on moderate-size road networks. Due to the use of the Euclidean metric as classifying metric, the approach allows for several variants of Dijkstra, in particular a natural goal-directed (unidirectional) version as well as efficient one-to-many shortest path queries. The (compared to later work) less competitive running times, both for the pre-processing phase as well as the queries are mostly due to the lack of an efficient compression scheme, which (in particular for the networks induced by higher level edges) improves the processing time considerably.
An article by Sanders and Schultes (“Engineering highway hierarchies”. In: Proceedings of the 14th European Symposium on Algorithms ESA '06, pages 804-816, 2006) adopts a different classifying metric. In an ordinary Dijkstra computation from a source, the r-th node settled may be said to have Dijkstra rank r with respect to the source. The article defines the level of an edge as being high if it is on a shortest path between some source and target such that one node of the edge has high Dijkstra rank with respect to the source and the other node of the edge has high Dijkstra rank with respect to the target. The article achieves an improvement of an order of magnitude both in pre-processing time as well as query times, mainly because of a highly efficient compression and pruning scheme in the higher levels of the network. The output of the algorithm is a path containing compressed edges. However, it is not clear how much effort in both time and space is necessary to uncompress those edges. The presented variant is also inherently bidirectional, so both goal-direction as well as one-to-many queries are not easily added.
In an article by Goldberg et al. (“Reach for A*: Efficient point-to-point shortest path algorithms”. In: Proceedings of the 8th Workshop on Algorithm Engineering and Experiments ALENEX '06, 2006) edge levels are combined with a compression scheme and lower bounds are used, based on pre-computed distances to a few landmarks, to allow for a more goal-directed search. Running times are reported that are comparable to those presented in the above-cited article by Sanders et al. However, the space consumption is higher, because every node in the network has to store distances to all landmarks.
Articles by Möhring et al. (“Acceleration of shortest path and constrained shortest path computation”. In: Proceedings of the 4th Workshop on Experimental and Efficient Algorithms, WEA '05, pages 126-138, 2005 and “Partitioning graphs to speed up Dijkstra's algorithm”. In: Proceedings of the 4th Workshop on Experimental and Efficient Algorithms WEA '05, pages 189-202, 2005) and, in independent work, Lauther (“An extremely fast, exact algorithm for finding shortest paths in static networks with geographical background”. In: Münster GI-Tage, 2004) explored edge signs as a means to achieve very fast query times. Intuitively, an edge sign says whether that edge is on a shortest path to a particular region of the graph. In an extreme case, an edge could have a sign to every node on the shortest path to which it lies. A shortest path query could then be answered by simply following the signs to the target without any detour.
However, to pre-compute these perfect signs requires an all-pairs shortest-path computation, which takes quadratic time and would be infeasible already for a small portion of the whole road network, e.g. the road network of California. In the cited articles, it is shown how to cut down on this pre-processing, by putting up signs to sufficiently large regions of the graph, but pre-computation of those signs is still prohibitive for large networks.
It is therefore an object of the present invention to provide an improved method and device for determining the length of a shortest path in a network.